package com.berchen.test;

/**
 * 快速排序
 */
public class QuickSort {
    public static void main(String[] args) {

    }
    public static void quickSort(int[] arr,int start,int end ){
        int l=start,r=end,midValue=arr[(start+end)/2];

        while (l<r){
            // 找到大于等于中间值的数据
            while (arr[l]<midValue){
                l++;
            }
            // 找到小于等于中间值的数据
            while (arr[r]>midValue){
                r--;
            }
            if(l>=r){
                break;
            }
            // 交换
            int temp=arr[l];
            arr[l]=arr[r];
            arr[r]=temp;


            if(arr[l]==midValue){
                r--;
            }
            if(arr[r]==midValue){
                l++;
            }
        }
        if(l==r){
            l++;
            r--;
        }
        if(start<r){
            quickSort(arr,start,r);
        }
        if(l<end){
            quickSort(arr,l,end);
        }
    }
}
